package io.vector.study.algorithm.search;

import java.util.Objects;

/**
 * Created by vector on 2017/3/7.
 */
public class BinarySearch {

    public <T extends Comparable<? super T>> int search(T[] array, T target) {
        if (array == null || array.length == 0) {
            return -1;
        }

        return searchWithRange(array, 0, array.length - 1, target);
    }

    private <T extends Comparable<? super T>> int searchWithRange(T[] array, int fromIndex, int toIndex, T target) {
        if (fromIndex > toIndex) {
            return -1;
        }

        int low = fromIndex;
        int high = toIndex;
        int middle;
        while (low <= high) {
            middle = (low + high) / 2;
            int compareResult = compare(array[middle], target);
            if (compareResult == 0) {
                return middle;
            } else if (compareResult > 0) {
                high = middle - 1;
            } else {
                low = middle + 1;
            }
        }
        return -1;
    }

    private <T extends Comparable<? super T>> int compare(T object1, T object2) {
        if (Objects.equals(object1, object2)) {
            return 0;
        }

        if (Objects.isNull(object1)) {
            return -1;
        } else if (Objects.isNull(object2)) {
            return 1;
        } else {
            return object1.compareTo(object2);
        }
    }


}
